#include <iostream>
#include <vector>

using namespace std;

// 定义target在区间[a, b]中
int search(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {  // left == right时 middle也有定义
        int middle = (left + right) / 2;
        if (nums[middle] > target) {  // target落在左半边区域
            right = middle - 1;  // nums[middle]已经大于target了，middle这个位置索引可以剔出掉
        } else if (nums[middle] < target) {  // target落在右半边区域
            left = middle + 1;  // nums[middle]已经小于target了，middle这位置索引可以剔出掉
        } else {
            return middle;
        }
    }

    return -1;
}

// 定义target在区间[a, b)中
int search2(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while (left < right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] > target) {
            right = middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else {
            return middle;
        }
    }

    return -1;
}

int main() {
    vector<int> nums = {-1, 0, 3, 5, 9, 12};
    int target = 9;
    int result = search2(nums, target);

    cout << "reslut: " << result << endl;
}